package ch5.part12;

import java.util.Arrays;

/**
 * @author liuwanxiang
 * @version 2019/06/17
 */
public class FindLostNumber {

    /**
     * 无序数组里有99个不重复的正整数，范围为1..100，求缺失的那个整数
     * 时间复杂度：O(n) = n
     * 空间复杂度：O(n) = 1
     *
     * @param array 无序数组
     * @param start 范围的起始值
     * @param end   范围的结尾值
     * @return 缺失的正整数
     */
    private static int calc1(int[] array, int start, int end) {
        int totalSum = 0, arraySum = 0;
        for (int i = start; i <= end; i++) {
            totalSum += i;
        }
        for (int value : array) {
            arraySum += value;
        }
        return totalSum - arraySum;
    }

    /**
     * 无序数组里有若干个不重复的正整数，范围为1..100
     * 其中99个整数都出现了偶数次，某一个整数只出现了奇数次
     * 求奇数次的那个整数
     * 时间复杂度：O(n) = n
     * 空间复杂度：O(n) = 1
     *
     * @param array 无序数组
     * @return 出现奇数次的那个整数
     */
    private static int calc2(int[] array) {
        int result = 0;
        for (int value : array) {
            result = result ^ value;
        }
        return result;
    }

    /**
     * 无序数组里有若干个不重复的正整数，范围为1..100
     * 其中98个整数都出现了偶数次，剩下的两个整数只出现了奇数次
     * 求奇数次的那两个整数
     * 时间复杂度：O(n) = n
     * 空间复杂度：O(n) = 1
     *
     * @param array 无序数组
     * @return 出现奇数次的那个整数
     */
    private static int[] calc3(int[] array) {
        int[] result = new int[2];

        // 1. 第一次进行异或运算，得到result[0]^result[1]的结果
        int xorResult = 0;
        for (int value : array) {
            xorResult = xorResult ^ value;
        }
        if (xorResult == 0) {
            return null;
        }

        // 2. 确定result[0]、result[1]两个数的不同位，以此做分组求解
        int separator = 1;
        while (0 == (xorResult & separator)) {
            separator <<= 1;
        }

        // 3. 根据标志位的不同，进行分组异或，得到结果
        for (int value : array) {
            if ((value & separator) == 0) {
                result[0] = result[0] ^ value;
            } else {
                result[1] = result[1] ^ value;
            }
        }

        return result;
    }


    public static void main(String[] args) {
        int result = calc1(new int[]{2, 7, 1, 3, 6, 4}, 1, 7);
        System.out.println(result);

        result = calc2(new int[]{1, 4, 2, 3, 4, 2, 1});
        System.out.println(result);

        System.out.println(Arrays.toString(calc3(new int[]{1, 4, 2, 3, 4, 2, 1, 1})));

    }

}
